package matrix;
public class searchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (target<matrix[0][0]) {
            return false;
        }
        //循环来遍历所有元素
        //定义mark数组
        int m=matrix.length,n=matrix[0].length;
        boolean[][] mark=new boolean[m][n];
        int x=0,y=0;
        while (x<m&&y<n) {
            if (matrix[x][y]==target) {
                return true;
            }
            //标记当前位置，然后移动
            //可能被逼到角落，这时候就要判断是否还有能走的，否则就退出
            if (y+1<n&&!mark[x][y+1]&&matrix[x][y+1]<=target) {
                y++;
                mark[x][y]=true;
            }else if (x+1<m&&!mark[x+1][y]&&matrix[x+1][y]<=target) {
                x++;
                mark[x][y]=true;
            }else{
                //只能往回推
                //往左
                if (y-1>=0) {
                    y--;
                }else if (x-1>=0) {
                    //往上
                    x--;
                }else{
                    //没法回退
                    return false;
                }
            }
        }
        // 对于没找到的情况
        return false;
    }
    public static void main(String[] args) {
        //{1,2,3}{8,9,10} target=4
        // int[][]matrix = new int[][]{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        // int[][]matrix = new int[][]{{1,4,7,11,15},{20,21,22,23,24}};
        int[][]matrix = new int[][]{{1}};
        System.out.println(searchMatrix(matrix, 16));
    }
    
}
